/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
// BFS
var cloneGraph = function (node) {
    if(!node) return
    // 是否访问过，visited用Map的原因是保存已经生成的节点
    const visited = new Map()
    const queue = [node]
    visited.set(node, new Node(node.val))
    // 队不空
    while(queue.length > 0) {
        let tempN = queue.shift()
        for(let i = 0; i < tempN.neighbors.length; i++) {
            let n = tempN.neighbors[i]
            if(!visited.has(n)) {
                queue.push(n)
                visited.set(n, new Node(n.val))
            }
            visited.get(tempN).neighbors.push(visited.get(n))
        }
    }
    return visited.get(node)
};